{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "breathing-programmer",
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import random\n",
    "from random import seed\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "reflected-traffic",
   "metadata": {},
   "outputs": [],
   "source": [
    "q = 32 # Ciphertext Modulus is 2**32 \n",
    "level = 3 # Decomposition level for the PBS\n",
    "base_log = 7 # Decomposition base log for the PBS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "gorgeous-sandwich",
   "metadata": {},
   "outputs": [],
   "source": [
    "def closest_representable(input_word, level, base_log):\n",
    "    ## Inputs: \n",
    "    ##  input_word to be \"rounded\", decomposition parameters level_count and base_log\n",
    "    ## Outputs: Computes the closest representable number by the decomposition defined by \n",
    "    ##  level_count and base_log.\n",
    "    non_rep_bit_count = q - level * base_log\n",
    "    non_rep_mask = 1 << (non_rep_bit_count - 1)\n",
    "    non_rep_bits = input_word & non_rep_mask\n",
    "    non_rep_msb = non_rep_bits >> (non_rep_bit_count - 1)\n",
    "    res = input_word >> non_rep_bit_count\n",
    "    res = res + non_rep_msb\n",
    "    res = res << non_rep_bit_count\n",
    "    return res\n",
    "\n",
    "def decompose_input(decomp_input, level_l, base_log):\n",
    "    ## Inputs: \n",
    "    ##  Coefficient decomp_input to be decomposed with decomposition parameters level_l and base_log\n",
    "    ## Output: list of level_l coefficients representing the closest representable number\n",
    "    closest_representable_input = closest_representable(decomp_input, level_l, base_log) % 2**q\n",
    "    #print(\"Closest representable input: \", hex(closest_representable_input))\n",
    "    current_level = level_l\n",
    "    state = closest_representable_input >> (q - base_log * level_l)\n",
    "    mod_b_mask = (1 << base_log) - 1\n",
    "    decomposed_input = [0]*level_l\n",
    "    for i in range(level_l):\n",
    "        #print(\"Current level: \", current_level)\n",
    "        # Decompose the current level\n",
    "        decomp_output = state & mod_b_mask\n",
    "        #print(\"decomp out tmp: \", hex(decomp_output))\n",
    "        state >>= base_log\n",
    "        carry = ((decomp_output-1) | state) & decomp_output\n",
    "        #print(\"Carry: \", hex(carry))\n",
    "        carry >>= base_log - 1\n",
    "        #print(\"Shifted Carry: \", hex(carry))\n",
    "        state += carry\n",
    "        decomp_output = decomp_output - (carry << base_log)\n",
    "        decomposed_input[current_level-1] = decomp_output\n",
    "        current_level -= 1\n",
    "        \n",
    "    # Reconstruct to check \n",
    "    recons = 0\n",
    "    for i in range(level_l):\n",
    "        recons += decomposed_input[i]*2**(32-(1+i)*base_log) % 2**32\n",
    "        print(\"reconstruction\", i, recons)\n",
    "    recons = recons % 2**q\n",
    "    if recons!=closest_representable_input: \n",
    "        print(\"problem decomposing\")\n",
    "        print(recons, \" \", closest_representable_input)\n",
    "    print(recons, \" \", closest_representable_input)\n",
    "\n",
    "    return decomposed_input"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "closing-accused",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "reconstruction 0 2617245696\n",
      "reconstruction 1 2617245696\n",
      "reconstruction 2 6912208896\n",
      "2617241600   2617241600\n",
      "Decomposition of  2617242525  is  [-50, 0, -2]\n"
     ]
    }
   ],
   "source": [
    "# Generate test vectors\n",
    "2617242525\n",
    "decomposition = decompose_input(2617242525, 3, 7)\n",
    "print(\"Decomposition of \", \"2617242525\" , \" is \", decomposition)\n",
    "\n",
    "# decomposition = decompose_input(int(\"0x187fc55f\",16), 3, 7)\n",
    "# print(\"Decomposition of \", \"0xF87fc55f\" , \" is \", decomposition)\n",
    "\n",
    "# decomposition = decompose_input(int(\"0xe07fa59b\",16), 3, 7)\n",
    "# print(\"Decomposition of \", \"0xe07fa59b\" , \" is \", decomposition)\n",
    "# print(\"----------------------------------------\")\n",
    "\n",
    "# decomposition = decompose_input(int(\"0x7f9d0e65\",16), 3, 7)\n",
    "# print(\"Decomposition of \", \"0x7f9d0e65\" , \" is \", decomposition)\n",
    "# print(\"----------------------------------------\")\n",
    "\n",
    "# decomposition = decompose_input(int(\"0x5f08769\",16), 3, 7)\n",
    "# print(\"Decomposition of \", \"0x5f08769\" , \" is \", decomposition)\n",
    "# print(\"----------------------------------------\")\n",
    "\n",
    "# decomposition = decompose_input(int(\"0x1fea30de\",16), 3, 7)\n",
    "# print(\"Decomposition of \", \"0x1fea30de\" , \" is \", decomposition)\n",
    "# print(\"----------------------------------------\")\n",
    "\n",
    "# decomposition = decompose_input(int(\"0x81f7631\",16), 3, 7)\n",
    "# print(\"Decomposition of \", \"0x81f7631\" , \" is \", decomposition)\n",
    "# print(\"----------------------------------------\")\n",
    "\n",
    "# decomposition = decompose_input(int(\"0xd0b0d0f7\",16), 3, 7)\n",
    "# print(\"Decomposition of \", \"0xd0b0d0f7\" , \" is \", decomposition)\n",
    "# print(\"----------------------------------------\")\n",
    "\n",
    "# decomposition = decompose_input(int(\"0x913685b5\",16), 3, 7)\n",
    "# print(\"Decomposition of \", \"0x913685b5\" , \" is \", decomposition)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.4 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.4"
  },
  "vscode": {
   "interpreter": {
    "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
